#include <iostream>
#include "util.h"
#include <cmath>
#include <ctime>

using namespace std;
template <typename T>

int binarySearch(T arr[], int n, T target){

    //[L ... R]
    int L = 0;
    int R = n - 1;
    while (L <= R){

        int mid = L + (R - L)/2;
        if (arr[mid] == target)
            return mid;
        if (arr[mid] < target)
            L = mid + 1;
        if (arr[mid] > target)
            R = mid - 1;
    }
    return -1;
}

int main() {
    int n = pow(10, 6);
    int *data = MyUtil::generateOrderedArray(n);
    clock_t start = clock();
    cout << "start: " << endl;
    for (int i = 0; i < n; i++) {
        assert(i == binarySearch(data, n, i));
    }
    clock_t end = clock();
    cout << "Binary Search Test Complete." << endl;
    cout << "Time cost: " << double(end - start)/CLOCKS_PER_SEC<< endl;

    return 0;
}